#include <bits/stdc++.h>

using namespace std;

class SelectBubbleInsert
{
public:
    // 数组中交换i和j位置的数
    void swap(vector<int>& arr, int i, int j)
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 选择排序
    void selectionSort(vector<int>& arr)
    {
        if(arr.size() < 2) return;
        // 0 ~ 0
        // 0 ~ 1
        // ...
        // 0 ~ n - 2
        // 0 ~ n - 1
        // 每次选一个最小的数放到 i 位置上
        for(int minIndex, i = 0; i < arr.size() - 1; ++i)
        {
            minIndex = i;
            for(int j = i + 1; j < arr.size(); ++j)
            {
                if(arr[j] < arr[minIndex]) minIndex = j;
            }
            swap(arr, i, minIndex);
        }
    }

    // 冒泡排序
    void bubbleSort(vector<int>& arr)
    {
        if(arr.size() < 2) return;
        // 每一趟排序，冒一个数到 end 位置
        // 0 ~ n - 1
        // 0 ~ n - 2
        // ....
        // 0 ~ end
        // 0 ~ 1
        for(int end = arr.size() - 1; end > 0; --end)
        {
            for(int i = 0; i < end; ++i)
            {
                if(arr[i] > arr[i + 1]) swap(arr, i, i + 1);
            }
        }
    }

    // 插入排序
    void insertionSort(vector<int>& arr)
    {
        if(arr.size() < 2) return;
        for(int i = 1; i < arr.size(); ++i)
        {
            // [0, j] 已经有序了，此时插入 arr[j + 1]
            for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; --j)
            {
                swap(arr, j, j + 1);
            }
        }
    }
};


// 为了测试
// 生成长度为n，值在[-v, +v]之间的随机数组
vector<int> randomArray(int n, int v)
{
    vector<int> arr(n);
    for (int i = 0; i < n; ++i)
    {
        arr[i] = rand() % (2 * v + 1) - v;
    }
    return arr;
}

// 为了测试
// 对数器
int main()
{
    srand(time(nullptr));
    int n = 200;
    int v = 1000;
    int testTime = 10000;
    SelectBubbleInsert t;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTime; i++)
    {
        int len = rand() % n;
        vector<int>&& nums1 = randomArray(len, v);
        vector<int> nums2(nums1), nums3(nums1);
        int k = rand() % n + 1;
        t.selectionSort(nums1);
        t.bubbleSort(nums2);
        t.insertionSort(nums3);
        if (nums1 != nums2 || nums1 != nums3 || nums2 != nums3)
        {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;

    return 0;
}